//找出字符串中子串的下标 力扣28
//KMP算法 前缀表 最长相等前后缀
class Solution {
public:
	
	void getnext(vector<int>& next,string s)
	{
		int j = 0;
		next[0] = 0;
		for(int i = 1; i < s.size(); i++)
		{
			while(j > 0 && s[j] != s[i])
			{
				j = next[j-1];
			}
			if(s[j] == s[i])
			{
				j++;
			}     
			next[i] = j;
			
		}
	}
	
	int strStr(string haystack, string needle) {
		if(needle.size() == 0) return 0;
		
		vector<int> next(needle.size());
		getnext(next,needle);
		
		for(int i = 0,j = 0; i < haystack.size(); i++)
		{
			while(j > 0 && needle[j] != haystack[i])
			{
				j = next[j-1];
			}
			if(needle[j] == haystack[i])
			{
				j++;
			}
			if(j == needle.size()) return i - needle.size() + 1;
			
		}
		return -1;
	}
};
